// https://leetcode.cn/problems/max-area-of-island/description/

// 算法思路总结：
// 1. 广度优先搜索计算岛屿最大面积
// 2. 遍历网格，对未访问的陆地启动BFS
// 3. 使用方向数组进行四方向扩展
// 4. 统计每个连通区域的面积并更新最大值
// 5. 全局vis数组配合memset重置访问状态
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    typedef pair<int, int> PII;
    bool vis[51][51] = {false};
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int m, n;
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        memset(vis, 0, sizeof(vis));
        int ret = 0;

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] == 1 && vis[i][j] == false)
                {
                    int square = bfs(i, j, grid);
                    ret = max(ret, square);
                }
            }
        }
        
        return ret;
    }

    int bfs(int i, int j, vector<vector<int>>& grid)
    {
        queue<PII> q;
        q.push({i, j});
        vis[i][j] = true;

        int square = 1;
        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && grid[x][y] == 1)
                {
                    q.push({x, y});
                    vis[x][y] = true;
                    square++;
                }
            }
        }

        return square;
    }
};

int main()
{
    vector<vector<int>> grid1 = {
        {0,0,1,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,1,1,1,0,0,0},
        {0,1,1,0,1,0,0,0,0,0,0,0,0},
        {0,1,0,0,1,1,0,0,1,0,1,0,0},
        {0,1,0,0,1,1,0,0,1,1,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,0,1,1,1,0,0,0},
        {0,0,0,0,0,0,0,1,1,0,0,0,0}
    };

    vector<vector<int>> grid2 = {
        {0,0,0,0,0,0,0,0}
    };

    Solution sol;
    cout << sol.maxAreaOfIsland(grid1) << endl;
    cout << sol.maxAreaOfIsland(grid2) << endl;

    return 0;
}